package com.lw.leetcode.sort.b;

import java.util.Arrays;

/**
 * arr
 * 面试题 16.16. 部分排序
 *
 * @Author liw
 * @Date 2021/7/12 17:13
 * @Version 1.0
 */
public class SubSort {

    public static void main(String[] args) {
        SubSort test = new SubSort();
        // 3,9
//        int[] arr = {1,2,4,7,10,11,7,12,6,7,16,17,19};
        // 1,11
//        int[] arr = {1,2,4,7,10,11,7,12,6,7,16,1,19};
        // [-1, -1]
//        int[] arr = {1, 2, 3, 4, 5};
        // [-1, -1]
        int[] arr = {1};
        int[] aa = test.subSort(arr);
        System.out.println(Arrays.toString(aa));
    }

    public int[] subSort(int[] array) {
        int length = array.length;
        int max = Integer.MIN_VALUE;
        int end = -1;
        int min = Integer.MAX_VALUE;
        int st = -1;
        for (int i = 0; i < length; i++) {
            if (array[i] < max) {
                end = i;
            }
            max = Math.max(max, array[i]);
            if (array[length - 1 - i] > min) {
                st = length - 1 - i;
            }
            min = Math.min(min, array[length - 1 - i]);
        }
        return new int[]{st, end};
    }

    public int[] subSort2(int[] array) {
        int length = array.length;
        if (length < 2) {
            return new int[]{-1, -1};
        }
        int m = Integer.MIN_VALUE;
        int end = -1;
        for (int i = 0; i < length; i++) {
            if (array[i] < m) {
                end = i;
            }
            m = Math.max(m, array[i]);
        }
        m = Integer.MAX_VALUE;
        int st = -1;
        for (int i = length - 1; i >= 0; i--) {
            if (array[i] > m) {
                st = i;
            }
            m = Math.min(m, array[i]);
        }
        return new int[]{st, end};
    }


}
